|
A safe prime is a prime number of the form 2''p'' + 1, where ''p'' is also a prime. (Conversely, the prime ''p'' is a Sophie Germain prime.) The first few safe primes are : 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... With the exception of 7, a safe prime ''q'' is of the form 6''k'' − 1 or, equivalently, ''q'' ≡ 5 (mod 6) — as is ''p'' > 3 (c.f. Sophie Germain prime, second paragraph). Similarly, with the exception of 5, a safe prime ''q'' is of the form 4''k'' − 1 or, equivalently, ''q'' ≡ 3 (mod 4) — trivially true since (''q'' − 1) / 2 must evaluate to an odd natural number. Combining both forms using lcm(6,4) we determine that a safe prime ''q'' > 7 also must be of the form 12''k''−1 or, equivalently, ''q'' ≡ 11 (mod 12). == Applications == These primes are called "safe" because of their relationship to strong primes. A prime number ''q'' is a ''strong'' prime if and both have some large prime factors. For a safe prime , the number naturally has a large prime factor, namely ''p'', and so a safe prime ''q'' meets part of the criteria for being a strong prime. The running times of some methods of factoring a number with ''q'' as a prime factor depend partly on the size of the prime factors of . This is true, for instance, of the Pollard rho, +1 and −1 methods. Although the most efficient known integer factorization methods do not depend on the size of the prime factors of , this is nonetheless considered important in cryptography: for instance, the ANSI X9.31 standard 〔Cryptographically secure pseudorandom number generator〕 mandates that ''strong'' primes (not ''safe'' primes) be used for RSA moduli. Safe primes are also important in cryptography because of their use in discrete logarithm-based techniques like Diffie-Hellman key exchange. If is a safe prime, the multiplicative group of numbers modulo has a subgroup of large prime order. It is usually this prime-order subgroup that is desirable, and the reason for using safe primes is so that the modulus is as small as possible relative to ''p''. Safe primes obeying certain congruences can be used to generate pseudo-random numbers of use in Monte Carlo simulation. Safe primes are more time consuming to search for than strong primes, and for this reason they have been less used. However, as computers get faster safe primes are being used more. Finding a 500-digit safe prime, like is now quite practical. The problem is that safe primes have the same low density as twin primes. For example, the smallest k such that 225 + k is a safe prime is k = 1989, which means that finding it requires testing approximately 1989 numbers for primality. Apart from their low density, they are easier to find than strong primes, in that the programs are much simpler. It is not necessary to attempt the factorization of p-1. (If p-1 is difficult to factor, then p is rejected, and p + 2 is tried. This is repeated until p-1 factors easily. This will happen sooner than p would become a safe prime, on average, because primes p for which p-1 factors easily are fairly dense.) All of this is made possible by the fact that there are extremely fast probabilistic tests for primality, such as the Miller–Rabin primality test. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Safe prime」の詳細全文を読む スポンサード リンク
|